#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include "rlp_test.h"

#ifndef DEBUG
#define DEBUG printf
#endif

#define PATH	"iprange"

typedef unsigned char u8;
typedef unsigned int u32;

#define ARG_ERR	BUG_PRINT("function arguments invalid\n")

#define BUG_PRINT(fmt, args...) \
	printf("[BUG] %s(): " fmt, __FUNCTION__, ##args)

#define	assert(expr) \
do { \
	if(unlikely(!(expr))) {                                   \
		BUG_PRINT("(%s) Assertion failed!\n", #expr);	\
	} \
} while (0)



#define U16_MAX	0xffff
#define U32_MAX 0xffffffff

#define BIT_U16		0
#define BIT_U32		1

#define RT_MISS		0
#define RT_NO_MISS	1

#define MAXKEY(bittype) \
((bittype) == BIT_U16 ? U16_MAX : U32_MAX)

#define get_u8(addr, offset) 	(*((u8 *)(((u8 *)addr)+offset)))
#define get_u16(addr, offset) 	(*((u16 *)(((u8 *)addr)+offset)))
#define get_u32(addr, offset) 	(*((u32 *)(((u8 *)addr)+offset)))

/* Rlp data structure definition  */
struct gen_spec {
	unsigned rlp : 1;
};

struct locate_inf {
	u32 key;
	struct gen_spec **nextspec;
};

/* rlp header */
struct rlp_spec {
	unsigned rlp       :  1; // rlp identifier (must be 1)
	unsigned bittype   :  1; // {BIT_U16, BIT_U32}
	unsigned num       : 24; // number of elements in the rlp
	unsigned int size;

	struct gen_spec * (*locate)(const struct rlp_spec *spec,
				    void *packet);
};

typedef enum {
	RLP_OK	=  0,
	RLP_ERR	= -1
} rlp_error;

struct addr_range_info {
	struct in_addr left;
	struct in_addr right;
};

struct gen_spec *g_gen_spec = NULL;

#define KEYSIZE(bittype) (1 << ((bittype) + 1))
#define FIRST_KEY(spec)     ((void *) (spec) + sizeof(*(spec)))
#define FIRST_NEXTSPEC(spec) (FIRST_KEY(spec) +                              \
			      IPT_ALIGN((spec)->num * KEYSIZE((spec)->bittype)))
#define IS_ELEM(e)	(e == g_gen_spec)


/* Variable definition */
struct gen_spec *tree[4] = {NULL}; 
int g_flags = 0;


int str2iprange( const char *str, struct in_addr *left, struct in_addr *right )
{
	int ret = 1;
	char *p = NULL;

	p = strchr( str, '-' );
	if ( NULL == p ) {
		ret = 0;
		goto out;
	}

	*p = '\0';
	p++;	
	ret = inet_aton( str, left );
	if ( 0 == ret ) 
		goto out;

	ret = inet_aton( p, right );
	if ( 0 == ret ) 
		goto out;
	
out:
	return ret;
}

static inline u32
hipac_maxkey(u8 bittype)
{
	if (bittype == BIT_U16)
		return U16_MAX;
	return U32_MAX;
}

static inline int
u16_key_exists(const struct rlp_spec *spec, u32 key, struct locate_inf *inf,
                u32 *position)
{
	return 0;
}

static inline int
u32_key_exists(const struct rlp_spec *spec, u32 key, struct locate_inf *inf,
		u32 *position)
{
	const u32 *part = FIRST_KEY(spec);
	u32 left = 0;
	u32 right = spec->num - 1;
	u32 pos;

	while (left <= right) {
		pos = (left + right) >> 1;
		if (part[pos] < key) {
			left = pos + 1;
		} else if (pos && part[pos - 1] >= key) {
			right = pos - 1;
		} else {
			if (inf != NULL) {
				inf->key = part[pos];
				inf->nextspec = FIRST_NEXTSPEC(spec) +
					pos * sizeof(void *);
			}
			if (position != NULL) 
				*position = pos;

			return part[pos] == key;
		}
	}

	/* should never be reached */
	assert(1 == 0);

	return 0;
}

rlp_error
rlp_locate(const struct rlp_spec *spec, struct locate_inf *inf, u32 key)
{
	if (spec == NULL || inf == NULL) {
		ARG_ERR;
		return RLP_ERR;
	}

	switch (spec->bittype) {
	case BIT_U16:
		u16_key_exists(spec, key, inf, NULL);
		break;
	case BIT_U32:
		u32_key_exists(spec, key, inf, NULL);
		break;
	default:
		return RLP_ERR;
	}
	return RLP_OK;
}

#if 0
static struct gen_spec *
u32_locate(const struct rlp_spec *spec, void *packet)
{
	return NULL;
}
#endif

struct rlp_spec *
rlp_new(u8 bittype, u8 ins_num, const u32 key[],
	struct gen_spec *nextspec[])
{
	struct rlp_spec *new_rlp;
	unsigned int rlp_size;

	if (unlikely(bittype > BIT_U32 || key == NULL || nextspec == NULL ||
		     !(ins_num == 1 || ins_num == 2) ||
		     (ins_num == 1 && key[0] != hipac_maxkey(bittype)) ||
		     (ins_num == 2 && (key[0] >= key[1] ||
				       key[1] != hipac_maxkey(bittype))))) {
		ARG_ERR;
		return NULL;
	}

	rlp_size = sizeof(*new_rlp) + IPT_ALIGN(ins_num * KEYSIZE(bittype)) +
		   ins_num * sizeof(void *);

	new_rlp = (struct rlp_spec *)malloc(rlp_size);
			   
	if (new_rlp == NULL) {
		return NULL;
	}
	
	new_rlp->rlp = 1;
	new_rlp->bittype = bittype;
	new_rlp->num = ins_num;
	new_rlp->size = rlp_size;

	switch (bittype) {
	case BIT_U16: 
		break;

	case BIT_U32:{ 
		u32 *k = FIRST_KEY(new_rlp);
		struct gen_spec **s = FIRST_NEXTSPEC(new_rlp);
		//new_rlp->locate = u32_locate;
		k[0] = key[0];
		s[0] = nextspec[0];
		if (ins_num == 2) {
			k[1] = key[1];
			s[1] = nextspec[1];
		}
		break;
	}
	}
	return new_rlp;
}

rlp_error
rlp_insert(const struct rlp_spec *spec, u8 ins_num, const u32 key[],
	   struct gen_spec *nextspec[], struct rlp_spec **result)
{
	void *first_ksrc, *ksrc, *kdst, *nsrc, *ndst;
	struct gen_spec *lnspec[2];
	u32 pos[2], lkey[2];
	u32 i, ksize, nsize;
	unsigned int newrlp_size;

	if (unlikely(spec == NULL || key == NULL || nextspec == NULL ||
		     result == NULL || !(ins_num == 1 || ins_num == 2) ||
		     (ins_num == 1 &&
		      key[0] >= hipac_maxkey(spec->bittype)) ||
		     (ins_num == 2 &&
		      (key[0] >= key[1] ||
		       key[1] >= hipac_maxkey(spec->bittype))))) {
		ARG_ERR;
		return RLP_ERR;
	}

	switch (spec->bittype) {
	case BIT_U16: {
		break;
	}
	case BIT_U32: {
		u8 ct = 0;
		if (!u32_key_exists(spec, key[0], NULL, &pos[0])) {
			lkey[ct] = key[0];
			lnspec[ct++] = nextspec[0];
		}
		if (ins_num == 2 &&
		    !u32_key_exists(spec, key[1], NULL, &pos[ct])) {
			assert(ct == 0 || pos[0] <= pos[1]);
			lkey[ct] = key[1];
			lnspec[ct++] = nextspec[1];
		}
		assert(ins_num == ct);
		ins_num = ct;
		break;
	}
	}

	/* ins_num can be 0, 1 or 2 here */
	assert(ins_num == 1 || ins_num == 2);
	newrlp_size = sizeof(**result) +
		      IPT_ALIGN((spec->num+ins_num) * KEYSIZE(spec->bittype)) +
		      (spec->num + ins_num) * sizeof(void *);
	*result = (struct rlp_spec*)malloc(newrlp_size);

	if (*result == NULL)
		return RLP_ERR;

	memcpy(*result, spec, sizeof(*spec));
	(*result)->num += ins_num;
	(*result)->size = newrlp_size;

	first_ksrc = FIRST_KEY(spec);
	ksrc = first_ksrc;
	kdst = FIRST_KEY(*result);
	nsrc = FIRST_NEXTSPEC(spec);
	ndst = FIRST_NEXTSPEC(*result);
	for (i = 0; i < ins_num; i++) {
		ksize = (first_ksrc + pos[i] * KEYSIZE(spec->bittype)) - ksrc;	/* p1 to kp size */
		nsize = (ksize / KEYSIZE(spec->bittype)) * sizeof(void *);	/* p1 to kp number * sizeof(void*) */
		if (ksize > 0) {
			memcpy(kdst, ksrc, ksize);
			memcpy(ndst, nsrc, nsize);
		}
		ksrc += ksize;
		kdst += ksize;
		nsrc += nsize;
		ndst += nsize;
		switch (spec->bittype) {
		case BIT_U16:
			break;
		case BIT_U32:
			*(u32 *) kdst = lkey[i];
			break;
		}
		*(struct gen_spec **) ndst = lnspec[i];
		kdst += KEYSIZE(spec->bittype);
		ndst += sizeof(void *);
	}
	ksize = (spec->num - (ins_num == 0 ? 0 : pos[ins_num - 1])) *
		KEYSIZE(spec->bittype);
	assert(ksize > 0);
	nsize = (ksize / KEYSIZE(spec->bittype)) * sizeof(void *);
	memcpy(kdst, ksrc, ksize);
	memcpy(ndst, nsrc, nsize);

	return RLP_OK;
}

static inline rlp_error
segment_insert_help(struct locate_inf *inf, u8 *ins_num,
		struct gen_spec* new_nextspec[])
{
	rlp_error stat;

	if (*inf->nextspec == NULL) {
		new_nextspec[*ins_num] = *inf->nextspec;
	} else if (IS_ELEM(*inf->nextspec)) {
		new_nextspec[*ins_num] = g_gen_spec;
	}else {
		BUG_PRINT("Unknow the spec\n");
		return RLP_ERR;
	}

	(*ins_num)++;

	return RLP_OK;

}

static rlp_error
segment_insert(struct rlp_spec **spec, u32 left, u32 right)
{  	
	u8 ins_num = 0;
	struct gen_spec* new_nextspec[2] = {NULL, NULL};
	struct locate_inf inf;
	u32 new_key[2];
	rlp_error stat;

#if 1
	if (left > 0) {
		stat = rlp_locate(*spec, &inf, left - 1);
		if (stat != RLP_OK) {
			goto error;
		}
		if (inf.key != left - 1) {
			new_key[ins_num] = left - 1;
			stat = segment_insert_help(&inf, &ins_num, new_nextspec);
			if (stat != RLP_OK) {
				goto error;
			}
		}
	}
#else

	if (left > 0) {
		stat = rlp_locate(*spec, &inf, left);
		if (stat != RLP_OK) {
			goto error;
		}
		if (inf.key != left ) {
			new_key[ins_num] = left;
			stat = segment_insert_help(&inf, &ins_num, new_nextspec);
			if (stat != RLP_OK) {
				goto error;
			}
		}
	}
#endif
	stat = rlp_locate(*spec, &inf, right);
	if (stat != RLP_OK) {
		goto error;
	}

	if (inf.key != right) {
		new_key[ins_num] = right;
		stat = segment_insert_help(&inf, &ins_num, new_nextspec);
		if (stat != RLP_OK) {
			goto error;
		}
	}

	if (ins_num > 0) {
		struct rlp_spec *b;
		assert(ins_num == 1 || new_key[0] != new_key[1]);
		stat = rlp_insert(*spec, ins_num, new_key, new_nextspec, &b);
		if (stat != RLP_OK) {
			goto error;
		}
		free( *spec );
		*spec = b;
	} else {
		/* same left-right nothing */
	}

	return RLP_OK;

error:
	for (ins_num = 0; ins_num < 2; ins_num++)
		free( new_nextspec[ins_num] );
	return RLP_ERR;
}

static rlp_error
rlp_tree_insert( struct rlp_spec **spec, const struct addr_range_info *info )
{
	u8 bittype = BIT_U32;
	struct gen_spec *nextspec[] = {NULL};
	struct locate_inf inf;
	rlp_error stat;
	u32 left = ntohl(info->left.s_addr);
	u32 right = ntohl(info->right.s_addr);

	stat = segment_insert(spec, left, right);
	if (stat != RLP_OK)
		return stat;
	do {
		stat = rlp_locate(*spec, &inf, left);
		if (stat != RLP_OK) {
			return stat;
		}
		left  = inf.key + 1;

		*inf.nextspec = g_gen_spec;
		if (stat != RLP_OK) {
			return stat;
		}
	} while (inf.key < right);

	return RLP_OK;	
}

static void
rlp_printf( struct rlp_spec *spec )
{
	rlp_error stat;
	u32 key = 0;
	struct locate_inf inf;
printf( "0x%x###############################################\n", spec );
	do {
		stat = rlp_locate(spec, &inf, key);
		if ( RLP_ERR == stat ) 
			return ;
		
		printf( "DEBUG: key is[0x%x], ", inf.key );
		if ( *inf.nextspec == g_gen_spec )
			printf( "miss!!\n" );
		else
			printf( "No miss!\n" );
		key = inf.key +1;

	} while ( inf.key < MAXKEY(BIT_U32) );

printf( "0x%x###############################################\n", spec );
	return ;
}

/* Find key from rlp tree */
int rlp_find( struct rlp_spec *spec, struct in_addr *key  )
{
	rlp_error stat;
	int ret = 1;
	struct locate_inf inf;

	if ( spec == NULL )
		return -1;

	stat = rlp_locate( spec, &inf, ntohl(key->s_addr)) ;	
	if ( RLP_ERR == stat )
		return -1;

	if ( *inf.nextspec != g_gen_spec ) {
		printf( "No nonononono\n" );
		return 0;
	}

	return ret;
}

static rlp_error rlp_tree_init( struct rlp_spec **spec )
{
	u8 bittype = BIT_U32;
	struct gen_spec *nextspec[] = {NULL};
	u32 key = MAXKEY(bittype);
	rlp_error stat;

	*spec = rlp_new(bittype, 1, &key, nextspec);
	if (*spec == NULL) {
		return RLP_ERR;
	}

	return RLP_OK;
}

static void
rlp_tree_destroy( struct rlp_spec **tree )
{
	free( *tree );
	return ;
}
int main( int argc, char **argv )
{
	int ret = 0;
	char line[256];
	char line1[256];
	struct addr_range_info info;
	size_t size = 0;
	FILE *fp = NULL;
	struct in_addr key; 

	g_gen_spec = (struct gen_spec *)malloc( sizeof(struct gen_spec) );
	if ( NULL == g_gen_spec ) {
		perror( "malloc" );
		return -1;
	}

	if ( NULL == (fp = fopen(PATH, "r")) ) {
		perror( "fopen" );
		ret = -1;
		goto out;
	}

	rlp_tree_init( (struct rlp_spec**)&tree[0] );

	rlp_printf( (struct rlp_spec*)tree[0] );
	while ( fgets(line, sizeof(line), fp) ) {
		if ( *line == '#' || 0x0a == get_u8(line, 0) )
			continue;

		ret = str2iprange( line, &info.left, &info.right );
		if ( 0 == ret ) {
			perror( "str2iprange" );
			ret = -1;
			goto out;
		}

		rlp_tree_insert( (struct rlp_spec**)&tree[0], &info );
	}

	/* debug */

	rlp_printf( (struct rlp_spec*)tree[0] );
	
	inet_aton( argv[1], &key );
	ret = rlp_find( (struct rlp_spec*)tree[0], (struct in_addr *)&key );
	printf( "%s: %s\n", argv[1], (ret == 1) ? "miss":"no miss" );

	rlp_tree_destroy( (struct rlp_spec**)&tree[0] );

out:
	if ( g_gen_spec )
		free( g_gen_spec );
	if ( fp )
		fclose( fp );
	return ret;
}
